'''
FHQ Treap 动态空间实现
'''
import random


class Node:
    def __init__(self, key, value, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        self.priority = random.random()
    def __repr__(self):
        return f'key: {self.key}, value: {self.value}, priority: {self.priority:.5f}'


class TreapTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def split(self, root, key):
        if not root:
            return None, None
        if root.key <= key:
            left_sub, right_sub = self.split(root.right, key)   # 当前左侧都小于，去右侧继续看
            root.right = left_sub
            return root, right_sub
        else:
            left_sub, right_sub = self.split(root.left, key)
            root.left = right_sub
            return left_sub, root

    def merge(self, small_root, large_root):
        if not small_root: return large_root
        elif not large_root: return small_root
        else:
            if small_root.priority >= large_root.priority:
                small_root.right = self.merge(small_root.right, large_root)
                return small_root
            else:
                large_root.left = self.merge(small_root, large_root.left)
                return large_root

    def _get(self, node, k):
        if node is None:
            return None
        elif k < node.key:
            return self._get(node.left, k)
        elif k > node.key:
            return self._get(node.right, k)
        return node

    def _add(self, k, v):
        find = self._get(self.root, k)
        if find:
            find.value = v
        else:
            self.size += 1
            small_tree, large_tree = self.split(self.root, k)
            small_tree = self.merge(small_tree, Node(k, v))
            self.root = self.merge(small_tree, large_tree)

    def _delete(self, k):
        find = self._get(self.root, k)
        if not find:
            return
        self.size -= 1
        small_eq_tree, large_tree = self.split(self.root, k)
        small_tree, _ = self.split(small_eq_tree, k - 1)
        self.root = self.merge(small_tree, large_tree)

    # ******************** 基本api ****************************
    def get(self, key):
        target = self._get(self.root, key)
        if not target: raise KeyError(key)
        return target.value

    def get_size(self):
        return self.size

    __getitem__ = get
    __setitem__ = _add
    __delitem__ = _delete
    __len__ = get_size

    def floor(self, key):
        def f(root):
            if root is None: return float('-inf')
            if key < root.key:
                return f(root.left)
            elif key > root.key:
                return max(root.key, f(root.right))
            else:
                return root.key

        return f(self.root)

    def ceil(self, key):
        def f(root):
            if root is None: return float('inf')
            if key < root.key:
                return min(root.key, f(root.left))
            elif key > root.key:
                return f(root.right)
            else:
                return root.key

        return f(self.root)